Floyd–Rivest Algorithm
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the Floyd-Rivest algorithm is a
selection algorithm In computer science, a selection algorithm is an algorithm for finding the kth smallest value in a collection of ordered values, such as numbers. The value that it finds is called the order statistic. Selection includes as special cases the p ...
developed by Robert W. Floyd and Ronald L. Rivest that has an optimal expected number of comparisons within lower-order terms. It is functionally equivalent to
quickselect In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list, also known as the ''k''th order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and t ...
, but runs faster in practice on average. It has an expected running time of and an expected number of comparisons of . The algorithm was originally presented in a Stanford University technical report containing two papers, where it was referred to as SELECT and paired with PICK, or median of medians. It was subsequently published in
Communications of the ACM ''Communications of the ACM'' (''CACM'') is the monthly journal of the Association for Computing Machinery (ACM). History It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are i ...
, Volume 18: Issue 3.


Algorithm

The Floyd-Rivest algorithm is a
divide and conquer algorithm In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dir ...
, sharing many similarities with
quickselect In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list, also known as the ''k''th order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and t ...
. It uses sampling to help partition the list into three sets. It then recursively selects the ''k''th smallest element from the appropriate set. The general steps are: # Select a small random sample ''S'' from the list ''L''. # From ''S'', recursively select two elements, ''u'' and ''v'', such that ''u'' < ''v''. These two elements will be the pivots for the partition and are expected to contain the ''k''th smallest element of the entire list between them (in a sorted list). # Using ''u'' and ''v'', partition ''S'' into three sets: ''A'', ''B'', and ''C''. ''A'' will contain the elements with values less than ''u'', ''B'' will contain the elements with values between ''u'' and ''v'', and ''C'' will contain the elements with values greater than ''v''. # Partition the remaining elements in ''L'' (that is, the elements in ''L'' - ''S'') by comparing them to ''u'' or ''v'' and placing them into the appropriate set. If ''k'' is smaller than half the number of the elements in ''L'' rounded up, then the remaining elements should be compared to ''v'' first and then only to ''u'' if they are smaller than ''v''. Otherwise, the remaining elements should be compared to ''u'' first and only to ''v'' if they are greater than ''u''. # Based on the value of ''k'', apply the algorithm recursively to the appropriate set to select the ''k''th smallest element in ''L''. By using , ''S'', = Θ(''n''2/3 log1/3 ''n''), we can get expected comparisons. We can get expected comparisons by starting with a small ''S'' and repeatedly updating ''u'' and ''v'' to keep the size of ''B'' small enough (''O''(''n''1/2 log1/2 ''n'') at Θ(''n'') processed elements) without unacceptable risk of the desired element being outside of ''B''.


Pseudocode version

The following
pseudocode In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actio ...
rearranges the elements between left and right, such that for some value ''k'', where left ≤ ''k'' ≤ right, the ''k''th element in the list will contain the (''k'' − left + 1)th smallest value, with the ith element being less than or equal to the ''k''th for all left ≤ i ≤ k and the jth element being larger or equal to for k ≤ j ≤ right: // ''left is the left index for the interval'' // ''right is the right index for the interval'' // ''k is the desired index value, where array is the (k+1)th smallest element when left = 0'' function select(array, left, right, k) is while ''right'' > ''left'' do // ''Use select recursively to sample a smaller set of size s'' // ''the arbitrary constants 600 and 0.5 are used in the original'' // ''version to minimize execution time.'' if right − left > 600 then n := right − left + 1 i := k − left + 1 z := ln(n) s := 0.5 × exp(2 × z/3) sd := 0.5 × sqrt(z × s × (n − s)/n) × sign(i − n/2) newLeft := max(left, k − i × s/n + sd) newRight := min(right, k + (n − i) × s/n + sd) select(array, newLeft, newRight, k) // ''partition the elements between left and right around t'' t := array i := left j := right swap array eftand array if array ight> t then swap array ightand array eft while i < j do swap array and array i := i + 1 j := j − 1 while array < t do i := i + 1 while array > t do j := j − 1 if array eft= t then swap array eftand array else j := j + 1 swap array and array ight // ''Adjust left and right towards the boundaries of the subset'' // ''containing the (k − left + 1)th smallest element.'' if j ≤ k then left := j + 1 if k ≤ j then right := j − 1


See also

*
Quickselect In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list, also known as the ''k''th order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and t ...
*
Introselect In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance. Introselect is related ...
* Median of medians


References

* * * {{DEFAULTSORT:Floyd-Rivest algorithm Selection algorithms